%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This file is part of the book
%%
%% Algorithmic Graph Theory
%% http://code.google.com/p/graph-theory-algorithms-book/
%%
%% Copyright (C) 2009--2011 Minh Van Nguyen <nguyenminh2@gmail.com>
%%
%% See the file COPYING for copying conditions.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\DontPrintSemicolon
\SetAlgoNoLine
%%
%% input
\KwIn{A positive integer $n$.}
%%
%% output
\KwOut{A list $L$ containing all the permutations of
  $\{1, 2, \dots, n\}$ in increasing lexicographic order.}
\BlankLine
%%
%% algorithm body
$L \assign [\,]$\;
$c_i \assign i$ for $i = 1, 2, \dots, n$\;
$\append(L,\, c_1 c_2 \cdots c_n)$\;
\For{$i \assign 2, 3, \dots, n!$}{
  $m \assign n - 1$\;
  \While{$c_m > c_{m+1}$}{
    $m \assign m - 1$\;
  }
  $k \assign n$\;
  \While{$c_m > c_k$}{
    $k \assign k - 1$\;
  }
  swap the values of $c_m$ and $c_k$\;
  $p \assign m + 1$\;
  $q \assign n$\;
  \While{$p < q$}{
    swap the values of $c_p$ and $c_q$\;
    $p \assign p + 1$\;
    $q \assign q - 1$\;
  }
  $\append(L,\, c_1 c_2 \cdots c_n)$\;
}
\Return $L$\;
